"""
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
"""
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        if len(nums) < 4:
            return res
        if len(nums) == 4 and sum(nums)==target:
            res.append(nums)
            return res
        for i in range(len(nums)-3):
            if i >0 and nums[i] == nums[i-1]:
                continue
            for j in range(len(nums)-2):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                l,r =j+1,len(nums)-1
                while l<r:
                    sum_value =nums[i]+nums[j]+nums[l]+nums[r]
                    if sum_value == target:
                        res.append([nums[i],nums[j],nums[l],nums[r]])
                        l += 1
                        r -= 1
                        while l<r and nums[l]==nums[l-1]:
                            l+=1
                        while l<r and nums[r]== nums[r+1]:
                            r -= 1
                    elif  sum_value < target:
                        l += 1
                    else:
                        r -= 1
        return res


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        if len(nums) < 4: return res
        if len(nums) == 4 and sum(nums) == target:
            res.append(nums)
            return res
        for i in range(len(nums)-3):
            if i > 0 and nums[i] == nums[i-1]: continue
            for j in range(i+1,len(nums)-2):
                if j > i+1 and nums[j] == nums[j-1]: continue
                l,r = j+1, len(nums)-1
                while l < r:
                    sum_value = nums[i] + nums[j] + nums[l] + nums[r]
                    if sum_value == target:
                        res.append([nums[i],nums[j],nums[l],nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]: l += 1
                        while l < r and nums[r] == nums[r+1]: r -= 1
                    elif sum_value < target:
                        l += 1
                    else:
                        r -= 1
        return res